package com.kevin.algorithm;

import com.alibaba.fastjson.JSON;
import com.kevin.model.Location;
import com.kevin.utils.DistanceUtil;
import com.kevin.utils.MapUtils;
import com.kevin.utils.PointsRep;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @Description: 通过划分表格，将数据进行分格分析。选取相应的分堆。
 *  两种分堆方式：1：选择大堆作为核心堆，其他不在堆中的点将通过堆的重心进行计算，离哪个重心近归为哪个重心
 *              2: 将所有表格计算中心点，根据分组数进行堆融合，每次将中心离得最近的两个堆进行融合
 *
 * @author kevin
 * @version V1.0
 * @date 2019/2/13 10:08
 **/
public class TableRoute implements AlgorithmStrategy{
    private static final Logger LOGGER = LoggerFactory.getLogger(TableRoute.class);

    /**
     * 数据仓库
     */
    private PointsRep pointsRep;

    /**
     * 执行网格算法
     * @param pointsRep
     * @return
     */
    @Override
    public Location[][] execute(PointsRep pointsRep) {
        /**
         * 数据仓库赋值
         */
        this.pointsRep = pointsRep;

        /**
         * 表格数据
         */
        Location[][] tableLocation = getTable();

        LOGGER.info(JSON.toJSONString(tableLocation));

        //按点进行聚类
        //return getGroup(tableLocation);
        //按堆融合进行聚类
        return getGroupTwo(tableLocation);
    }

    /** --------- 1-拆分表-开始 --------- **/

    /**
     * 数据拆分成网格
     * @return
     */
    private Location[][] getTable(){
        /**
         * 获取最小最大经纬度，并且偏移一度，保证所有数据都在方格里
         */
        //获取最小经度
        double minLon = getMinLon(this.pointsRep.getPoints()) - 0.000001;
        //获取最大经度
        double maxLon = getMaxLon(this.pointsRep.getPoints()) + 0.000001;
        //获取最小纬度
        double minLat = getMinLat(this.pointsRep.getPoints()) - 0.000001;
        //获取最大纬度
        double maxLat = getMaxLat(this.pointsRep.getPoints()) + 0.000001;

        /**
         * 根据分组确定表格拆分行列
         * todo 当前按照均分，后续进行优化
         */
        int columnCount = getColumnCount(this.pointsRep.getGroup());

        /**
         * 获取区间，保留六位精度
         */
        //获取经度区间
        double lonInterval = (maxLon - minLon)/columnCount;
        //获取纬度区间
        double latInterval = (maxLat - minLat)/columnCount;

        /**
         * 获取拆分后的表格，仅包含下边界和左边界
         */
        List<Location>[][] locations = getTable(columnCount,this.pointsRep.getPoints(),minLon,maxLon,minLat,maxLat,BigDecimal.valueOf(lonInterval),BigDecimal.valueOf(latInterval));

        /**
         * 按照表格中经纬度点的数量，由高到低排序，生成二维数组
         */

        return getLocationArray(locations);
    }

    /**
     * 根据分组数和列表进行分组
     * 在经纬度左下角进行开始拆分表格
     * 数据处于边界位置的，仅包含左边界和下边界
     * @return
     */
    private List[][] getTable(int columnCount, List<Location> locations, double minLon, double maxLon, double minLat, double maxLat, BigDecimal lonInterval,BigDecimal latInterval){
        /**
         * 定义二维数组，保存每格数据
         */
        List<Location>[][] locationTable = new ArrayList[columnCount][columnCount];

        /**
         * 生成经纬度临时列表
         */
        List<Location> tempLocations = new ArrayList<>();
        for(Location location : locations){
            tempLocations.add(location);
        }

        /**
         * 循环变量 i:经度区间循环变量
         *        j:纬度区间循环变量
         */
        for(int i=0;i<(columnCount);i++){
            for(int j=0;j<columnCount;j++){
                //当前格最小经度
                double currMinLon = BigDecimal.valueOf(minLon ).add(lonInterval.multiply(new BigDecimal(i))).doubleValue();
                //当前格最大经度
                double currMaxLon = BigDecimal.valueOf(minLon ).add(lonInterval.multiply(new BigDecimal(i))).add(lonInterval).doubleValue();
                if(i == (columnCount-1)){
                    currMaxLon = maxLon;
                }

                //当前格最小纬度
                double currMinLat = BigDecimal.valueOf(minLat).add(latInterval.multiply(new BigDecimal(j))).doubleValue();
                //当前格最大纬度
                double currMaxLat = BigDecimal.valueOf(minLat).add(latInterval.multiply(new BigDecimal(j))).add(latInterval).doubleValue();
                if(j == (columnCount-1)){
                    currMaxLat = maxLat;
                }

                /**
                 * 将数据分别放置到各个表格中
                 * 已经选中的数据将会在临时变量中移除
                 */
                Iterator<Location> iterator = tempLocations.iterator();
                while(iterator.hasNext()){
                    Location locat = iterator.next();

                    if(locationTable[i][j] == null){
                        locationTable[i][j] = new ArrayList<Location>();
                    }

                    if(locat.getLon()>=currMinLon && locat.getLon()<currMaxLon && locat.getLat()>=currMinLat && locat.getLat()<currMaxLat){
                        locationTable[i][j].add(locat);

                        //移除已经被选中的数据
                        iterator.remove();
                    }
                }

            }
        }

        return locationTable;
    }

    /**
     * 根据拆分好的表格数据，生成二维数组
     * @return
     */
    private Location[][] getLocationArray(List<Location>[][] locations){
        List<List<Location>> list = new ArrayList<>();

        //列表长度
        int listLen = 0;

        /**
         * 将所有表格数据放置到临时变量中
         */
        List<Location>[][] tempArray = new ArrayList[locations.length][locations[0].length];
        for(int i=0;i<locations.length;i++){
            for(int j=0;j<locations[i].length;j++){
                tempArray[i][j] = locations[i][j];
                //确定有多少有数据的表格
                if(locations[i][j] !=null && locations[i][j].size()>0){
                    listLen++;
                }
            }
        }

        /**
         * 将所有数据由大到小放置到列表中
         */
        for(int i=0;i<listLen;i++){
            //表格内数据量大小
            int size = -1;
            //表格x轴坐标
            int indexA = 0;
            //表格y轴坐标
            int indexB = 0;

            for(int a=0;a<tempArray.length;a++){
                for(int b=0;b<tempArray[a].length;b++){
                    if(size == -1){
                        if(tempArray[a][b]!=null){
                            size = tempArray[a][b].size();
                        }else{
                            size = 0;
                        }
                        indexA = a;
                        indexB = b;
                    }else if(tempArray[a][b]!=null && size < tempArray[a][b].size()){
                        size = tempArray[a][b].size();
                        indexA = a;
                        indexB = b;
                    }
                }

            }

            list.add(tempArray[indexA][indexB]);

            //将当前表格的数据置为null,保证已选择的数据不会再被选择
            tempArray[indexA][indexB] = null;
        }

        /**
         * 根据排好序的列表生成二维数组
         */
        if(list.size()>0 && list.get(0).size()>0){
            int lenA = list.size();
            int lenB = list.get(0).size();

            Location[][] locationArray = new Location[lenA][lenB];

            for(int i=0;i<lenA;i++){
                for(int j=0;j<lenB;j++){
                    if(j < list.get(i).size()){
                        locationArray[i][j] = list.get(i).get(j);
                    }
                }
            }

            return locationArray;
        }

        return new Location[0][0];
    }

    /**
     * 获取最小经度
     */
    private double getMinLon(List<Location> locations){
        //最小经度
        double minLon = -1;
        for(Location location : locations){
            if(minLon == -1){
                minLon = location.getLon();
            }else if(minLon > location.getLon()){
                minLon = location.getLon();
            }
        }

        return minLon;
    }

    /**
     * 获取最大经度
     * @param locations
     * @return
     */
    private double getMaxLon(List<Location> locations){
        //最大经度
        double maxLon = -1;
        for(Location location : locations){
            if(maxLon == -1){
                maxLon = location.getLon();
            }else if(maxLon < location.getLon()){
                maxLon = location.getLon();
            }
        }

        return maxLon;
    }

    /**
     * 获取最小纬度
     */
    private double getMinLat(List<Location> locations){
        //最小纬度
        double minLat = -1;
        for(Location location : locations){
            if(minLat == -1){
                minLat = location.getLat();
            }else if(minLat > location.getLat()){
                minLat = location.getLat();
            }
        }

        return minLat;
    }

    /**
     * 获取最大纬度
     * @param locations
     * @return
     */
    private double getMaxLat(List<Location> locations){
        //最大纬度
        double maxLat = -1;
        for(Location location : locations){
            if(maxLat == -1){
                maxLat = location.getLat();
            }else if(maxLat < location.getLat()){
                maxLat = location.getLat();
            }
        }

        return maxLat;
    }


    /**
     * 根据分组数获取需要拆分成 a x a（几乘几）的表格
     * todo 优化，需要根据具体数据量分布等决定经纬度表拆分成几乘几的表格。当前先按照均分进行拆分
     * @return
     */
    private int getColumnCount(int groupCount){
        /*int columnsNum = 0;

        for(int i=1;i<=groupCount;i++){
            if(((i/2)*(i/2))>=groupCount){
                columnsNum = i;
                break;
            }
        }

        return columnsNum;*/

        return groupCount*groupCount;
    }

    /** --------- 1-拆分表-结束 --------- **/

    /** --------- 2-根据表格聚类-开始 --------- **/

    /**
     * 根据最大的表格数据进行聚类
     * @param locations
     * @return
     */
    private Location[][] getGroup(Location[][] locations){
        //需要分组数
        int groupNum = this.pointsRep.getGroup();

        Location[][] finishGroup = null;
        /**
         * 判断聚类时是进行表格拆分，还是在现有表格上进行聚类运算
         */
        if(groupNum > locations.length){
            // TODO: 2019/2/13 分组数大于现有的有数据的表格数，需要对表格数进行拆分,暂时不做
        }else{
            /*
                获取各分组的中心点
             */
            Location[] centLocations = new Location[groupNum];

            for(int i=0;i<groupNum;i++){
                /**
                 * 将二维数组中每一行转化成list
                 */
                List<Location> tempList = new ArrayList<>();
                for(int j=0;j<locations[i].length;j++){
                    if(locations[i][j] != null){
                        tempList.add(locations[i][j]);
                    }else{
                        break;
                    }
                }
                centLocations[i] = MapUtils.getCenterPoint(tempList);
            }

            //返回聚类结果
            finishGroup = getGroup(centLocations,locations);

        }

        /**
         * 判断是否成功进行聚类运算，异常的话返回空的数据
         */
        if(finishGroup == null){
            finishGroup = new Location[0][0];
        }

        return finishGroup;
    }

    /**
     * @Description: 根据中心点 和 表格数据进行聚类
     *
     * @param
     * @return
     **/
    private Location[][] getGroup(Location[] centers,Location[][] locations){
        /**
         * 将初始堆转换成list格式
         */
        List<List<Location>> stackData = new ArrayList<>();

        for(int i=0;i<centers.length;i++){
            List<Location> locatList = new ArrayList<>();
            for(int j=0;j<locations[i].length;j++){
                if(locations[i][j] != null){
                    locatList.add(locations[i][j]);
                }else{
                    break;
                }
            }

            stackData.add(locatList);
        }

        /**
         * 将不在初始堆中的数据放置到一个list中，默认为非堆数据
         */
        List<Location> unStackData = new ArrayList<>();
        if(locations.length>centers.length){
            for(int i=centers.length;i<locations.length;i++){
                for(int j=0;j<locations[i].length;j++){
                    if(locations[i][j] != null){
                        unStackData.add(locations[i][j]);
                    }else{
                        break;
                    }
                }
            }
        }

        /**
         * 数据聚集
         */
        groupDataTypeOne(centers,stackData,unStackData);

        /**
         * 将聚集的数据转换成二维数组
         */
        //计算二维数组第二维长度
        int index = -1;
        for(List<Location> list : stackData){
            if(index == -1){
                index = list.size();
            }else if(index < list.size()){
                index = list.size();
            }
        }
        Location[][] finishGroup = new Location[stackData.size()][index];

        for(int i=0;i<stackData.size();i++){
            for(int j = 0; j < stackData.get(i).size();j++){
                finishGroup[i][j] = stackData.get(i).get(j);
            }
        }

        return finishGroup;
    }

    /**
     * 根据中心将非堆数据放置到堆  方式一
     * @return
     */
    private void groupDataTypeOne(Location[] centers, List<List<Location>> stackData, List<Location> unStackData){
        /**
         * 对比所有未在堆中的数据距离各中心点的距离，选取距离最短的，将点归到该堆
         */
        //未归堆点下标
        int unStackIndex = 0;
        //中心点下标
        int centerIndex = 0;
        //未归堆点到中心点最小距离
        double distance = -1;

        for(int i=0;i<unStackData.size();i++){
            for(int j=0;j<centers.length;j++){
                double currDistance = Double.valueOf(DistanceUtil.algorithm(unStackData.get(i).getLon(),unStackData.get(i).getLat(),centers[j].getLon(),centers[j].getLat()));
                if(distance == -1){
                    distance = currDistance;
                    unStackIndex = i;
                    centerIndex = j;
                }else if(currDistance < distance){
                    distance = currDistance;
                    unStackIndex = i;
                    centerIndex = j;
                }
            }

        }

        //将未归堆的点归堆
        stackData.get(centerIndex).add(unStackData.get(unStackIndex));
        //在未归堆中移除改点
        unStackData.remove(unStackIndex);
        /**
         * 重新计算已经归堆的点列表的中心点
         */
        centers[centerIndex] = MapUtils.getCenterPoint(stackData.get(centerIndex));

        /**
         * 如果还有未归堆点，继续归堆运算
         */
        if(unStackData.size() > 0){
            groupDataTypeOne(centers,stackData,unStackData);
        }
    }

    /** --------- 2-根据表格聚类-结束 --------- **/


    /** --------- 3-根据表格聚类-中心点融合方法-开始 --------- **/

    /**
     * 根据最大的表格数据进行聚类
     * @param locations
     * @return
     */
    private Location[][] getGroupTwo(Location[][] locations){
        //需要分组数
        int groupNum = this.pointsRep.getGroup();

        Location[][] finishGroup = null;
        /**
         * 判断聚类时是进行表格拆分，还是在现有表格上进行聚类运算
         */
        if(groupNum > locations.length){
            // TODO: 2019/2/13 分组数大于现有的有数据的表格数，需要对表格数进行拆分,暂时不做
        }else{
            /*
                获取各分组的中心点
             */
            Location[] centLocations = new Location[locations.length];

            for(int i=0;i<locations.length;i++){
                /**
                 * 将二维数组中每一行转化成list
                 */
                List<Location> tempList = new ArrayList<>();
                for(int j=0;j<locations[i].length;j++){
                    if(locations[i][j] != null){
                        tempList.add(locations[i][j]);
                    }else{
                        break;
                    }
                }
                centLocations[i] = MapUtils.getCenterPoint(tempList);
            }

            //返回聚类结果
            finishGroup = getGroupTwo(centLocations,locations);

        }

        /**
         * 判断是否成功进行聚类运算，异常的话返回空的数据
         */
        if(finishGroup == null){
            finishGroup = new Location[0][0];
        }

        return finishGroup;
    }

    /**
     * @Description: 根据中心点 和 表格数据进行聚类
     *
     * @param
     * @return
     **/
    private Location[][] getGroupTwo(Location[] centers,Location[][] locations){
        /**
         * 将初始堆转换成list格式
         */
        List<List<Location>> stackData = new ArrayList<>();

        for(int i=0;i<centers.length;i++){
            List<Location> locatList = new ArrayList<>();
            for(int j=0;j<locations[i].length;j++){
                if(locations[i][j] != null){
                    locatList.add(locations[i][j]);
                }else{
                    break;
                }
            }

            stackData.add(locatList);
        }

        /**
         * 数据聚集-中心点融合
         */
        if(centers.length > this.pointsRep.getGroup()){
            groupDataTypeTwo(centers,stackData);
        }

        /**
         * 将聚集的数据转换成二维数组
         */
        //计算二维数组第二维长度
        int index = -1;
        for(List<Location> list : stackData){
            if(index == -1){
                index = list.size();
            }else if(index < list.size()){
                index = list.size();
            }
        }
        Location[][] finishGroup = new Location[stackData.size()][index];

        for(int i=0;i<stackData.size();i++){
            for(int j = 0; j < stackData.get(i).size();j++){
                finishGroup[i][j] = stackData.get(i).get(j);
            }
        }

        return finishGroup;
    }

    /**
     * 根据中心将非堆数据放置到堆  方式一
     * @return
     */
    private void groupDataTypeTwo(Location[] centers, List<List<Location>> stackData){
        /**
         * 对比所有未在堆中的数据距离各中心点的距离，选取距离最短的，将点归到该堆
         */
        //第一个堆中心点下标
        int centerIndexA = 0;
        //第二个堆中心点下标
        int centerIndexB = 0;

        //中心点之间最小距离
        double distance = -1;

        for(int i=0;i<stackData.size();i++){
            for(int j=i+1;j<stackData.size();j++){
                double currDistance = Double.valueOf(DistanceUtil.algorithm(centers[i].getLon(),centers[i].getLat(),centers[j].getLon(),centers[j].getLat()));

                if(distance == -1){
                    distance = currDistance;
                    centerIndexA = i;
                    centerIndexB = j;
                }else if(currDistance < distance){
                    distance = currDistance;
                    centerIndexA = i;
                    centerIndexB = j;
                }
            }

        }

        //将未归堆的点归堆
        stackData.get(centerIndexA).addAll(stackData.get(centerIndexB));
        //在未归堆中移除改点
        stackData.remove(centerIndexB);
        /**
         * 重新计算已经归堆的点列表的中心点
         */
        centers[centerIndexA] = MapUtils.getCenterPoint(stackData.get(centerIndexA));

        Location[] reGenCenters = new Location[stackData.size()];
        int index = 0;
        for(int i=0;i<reGenCenters.length;i++){
            if(index == centerIndexB){
                index++;
                reGenCenters[i] = centers[index];
            }else{
                reGenCenters[i] = centers[index];
            }

            index++;
        }

        /**
         * 如果还有未归堆点，继续归堆运算
         */
        if(reGenCenters.length > this.pointsRep.getGroup()){
            groupDataTypeTwo(reGenCenters,stackData);
        }
    }

    /** --------- 3-根据表格聚类-中心点融合方法-结束 --------- **/


}
